{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Escape a Large Maze"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #depth-first-search #breadth-first-search #array #hash-table"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #深度优先搜索 #广度优先搜索 #数组 #哈希表"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: isEscapePossible"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #逃离大迷宫"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>在一个 10<sup>6</sup> x 10<sup>6</sup> 的网格中，每个网格上方格的坐标为 <code>(x, y)</code> 。</p>\n",
    "\n",
    "<p>现在从源方格 <code>source = [s<sub>x</sub>, s<sub>y</sub>]</code> 开始出发，意图赶往目标方格 <code>target = [t<sub>x</sub>, t<sub>y</sub>]</code> 。数组 <code>blocked</code> 是封锁的方格列表，其中每个 <code>blocked[i] = [x<sub>i</sub>, y<sub>i</sub>]</code> 表示坐标为 <code>(x<sub>i</sub>, y<sub>i</sub>)</code> 的方格是禁止通行的。</p>\n",
    "\n",
    "<p>每次移动，都可以走到网格中在四个方向上相邻的方格，只要该方格 <strong>不</strong> 在给出的封锁列表 <code>blocked</code> 上。同时，不允许走出网格。</p>\n",
    "\n",
    "<p>只有在可以通过一系列的移动从源方格 <code>source</code> 到达目标方格 <code>target</code> 时才返回 <code>true</code>。否则，返回 <code>false</code>。</p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>blocked = [[0,1],[1,0]], source = [0,0], target = [0,2]\n",
    "<strong>输出：</strong>false\n",
    "<strong>解释：</strong>\n",
    "从源方格无法到达目标方格，因为我们无法在网格中移动。\n",
    "无法向北或者向东移动是因为方格禁止通行。\n",
    "无法向南或者向西移动是因为不能走出网格。</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>blocked = [], source = [0,0], target = [999999,999999]\n",
    "<strong>输出：</strong>true\n",
    "<strong>解释：</strong>\n",
    "因为没有方格被封锁，所以一定可以到达目标方格。\n",
    "</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>0 <= blocked.length <= 200</code></li>\n",
    "\t<li><code>blocked[i].length == 2</code></li>\n",
    "\t<li><code>0 <= x<sub>i</sub>, y<sub>i</sub> < 10<sup>6</sup></code></li>\n",
    "\t<li><code>source.length == target.length == 2</code></li>\n",
    "\t<li><code>0 <= s<sub>x</sub>, s<sub>y</sub>, t<sub>x</sub>, t<sub>y</sub> < 10<sup>6</sup></code></li>\n",
    "\t<li><code>source != target</code></li>\n",
    "\t<li>题目数据保证 <code>source</code> 和 <code>target</code> 不在封锁列表内</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [escape-a-large-maze](https://leetcode.cn/problems/escape-a-large-maze/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [escape-a-large-maze](https://leetcode.cn/problems/escape-a-large-maze/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[0,1],[1,0]]\\n[0,0]\\n[0,2]', '[]\\n[0,0]\\n[999999,999999]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isEscapePossible(self, blocked: List[List[int]], source: List[int], target: List[int]) -> bool:\n",
    "        if len(blocked) < 2:\n",
    "            return True\n",
    "            \n",
    "        BOUNDARY = 10**6\n",
    "\n",
    "        rows = sorted(set(pos[0] for pos in blocked) | {source[0], target[0]})\n",
    "        columns = sorted(set(pos[1] for pos in blocked) | {source[1], target[1]})\n",
    "        r_mapping, c_mapping = dict(), dict()\n",
    "\n",
    "        r_id = (0 if rows[0] == 0 else 1)\n",
    "        r_mapping[rows[0]] = r_id\n",
    "        for i in range(1, len(rows)):\n",
    "            r_id += (1 if rows[i] == rows[i - 1] + 1 else 2)\n",
    "            r_mapping[rows[i]] = r_id\n",
    "        if rows[-1] != BOUNDARY - 1:\n",
    "            r_id += 1\n",
    "\n",
    "        c_id = (0 if columns[0] == 0 else 1)\n",
    "        c_mapping[columns[0]] = c_id\n",
    "        for i in range(1, len(columns)):\n",
    "            c_id += (1 if columns[i] == columns[i - 1] + 1 else 2)\n",
    "            c_mapping[columns[i]] = c_id\n",
    "        if columns[-1] != BOUNDARY - 1:\n",
    "            c_id += 1\n",
    "\n",
    "        grid = [[0] * (c_id + 1) for _ in range(r_id + 1)]\n",
    "        for x, y in blocked:\n",
    "            grid[r_mapping[x]][c_mapping[y]] = 1\n",
    "        \n",
    "        sx, sy = r_mapping[source[0]], c_mapping[source[1]]\n",
    "        tx, ty = r_mapping[target[0]], c_mapping[target[1]]\n",
    "\n",
    "        q = deque([(sx, sy)])\n",
    "        grid[sx][sy] = 1\n",
    "        while q:\n",
    "            x, y = q.popleft()\n",
    "            for nx, ny in [(x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1)]:\n",
    "                if 0 <= nx <= r_id and 0 <= ny <= c_id and grid[nx][ny] != 1:\n",
    "                    if (nx, ny) == (tx, ty):\n",
    "                        return True\n",
    "                    q.append((nx, ny))\n",
    "                    grid[nx][ny] = 1\n",
    "        \n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "EDGE, MAX, BASE, DIR = int(1e6), int(1e5), 131, [(1, 0), (-1, 0), (0, 1), (0, -1)]\n",
    "class Solution:\n",
    "    def isEscapePossible(self, blocked: List[List[int]], source: List[int], target: List[int]) -> bool:\n",
    "        block = {p[0] * BASE + p[1] for p in blocked}\n",
    "        n = len(blocked)\n",
    "        MAX = n * (n-1)//2 # 可直接使用 1e5\n",
    "        def check(a, b):\n",
    "            vis = {a[0] * BASE + a[1]}\n",
    "            d = deque([a])\n",
    "            while len(d) and len(vis) <= MAX:\n",
    "                x, y = d.popleft()\n",
    "                if x == b[0] and y == b[1]:\n",
    "                    return True\n",
    "                for dx, dy in DIR:\n",
    "                    nx, ny = x + dx, y + dy\n",
    "                    if nx < 0 or nx >= EDGE or ny < 0 or ny >= EDGE:\n",
    "                        continue\n",
    "                    h = nx * BASE + ny\n",
    "                    if h in block or h in vis:\n",
    "                        continue\n",
    "                    d.append((nx, ny))\n",
    "                    vis.add(h)\n",
    "            return len(vis) > MAX\n",
    "        return check(source, target) and check(target, source)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "EDGE, MAX, BASE, DIR = int(1e6), int(1e5), 131, [(1, 0), (-1, 0), (0, 1), (0, -1)]\n",
    "class Solution:\n",
    "    def isEscapePossible(self, blocked: List[List[int]], source: List[int], target: List[int]) -> bool:\n",
    "        block = {p[0] * BASE + p[1] for p in blocked}\n",
    "        n = len(blocked)\n",
    "        MAX = n * (n-1)//2 # 可直接使用 1e5\n",
    "        def check(a, b):\n",
    "            vis = {a[0] * BASE + a[1]}\n",
    "            d = deque([a])\n",
    "            while len(d) and len(vis) <= MAX:\n",
    "                x, y = d.popleft()\n",
    "                if x == b[0] and y == b[1]:\n",
    "                    return True\n",
    "                for dx, dy in DIR:\n",
    "                    nx, ny = x + dx, y + dy\n",
    "                    if nx < 0 or nx >= EDGE or ny < 0 or ny >= EDGE:\n",
    "                        continue\n",
    "                    h = nx * BASE + ny\n",
    "                    if h in block or h in vis:\n",
    "                        continue\n",
    "                    d.append((nx, ny))\n",
    "                    vis.add(h)\n",
    "            return len(vis) > MAX\n",
    "        return check(source, target) and check(target, source)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isEscapePossible(self, blocked: List[List[int]], s: List[int], t: List[int]) -> bool:\n",
    "        ban, n, DIR = defaultdict(set), len(blocked), ((0, 1), (0, -1), (1, 0), (-1, 0))\n",
    "        for x, y in blocked: ban[x].add(y)\n",
    "        def check(u, v):\n",
    "            seen, q = defaultdict(set), [u]\n",
    "            while q:\n",
    "                x, y = q.pop()\n",
    "                for dx, dy in DIR:\n",
    "                    nx, ny = x + dx, y + dy\n",
    "                    if 0 <= nx < 1000000 and 0 <= ny < 1000000 and ny not in ban[nx] and ny not in seen[nx]:\n",
    "                        if [nx, ny] == v: return True\n",
    "                        if abs(nx - u[0]) + abs(ny - u[1]) > n: return True\n",
    "                        q.append([nx, ny])\n",
    "                        seen[nx].add(ny)\n",
    "            return False\n",
    "        return check(s, t) and check(t, s)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isEscapePossible(self, blocked: List[List[int]], source: List[int], target: List[int]) -> bool:\n",
    "        N = 10**6\n",
    "        if source==target:\n",
    "            return True\n",
    "        if len(blocked)<=1:\n",
    "            return True\n",
    "        from collections import deque\n",
    "        nb = len(blocked)\n",
    "        max_arrive = nb*(nb-1)/2\n",
    "        \n",
    "        def bfs(start, ends):\n",
    "            D = deque([start])\n",
    "            vis = set()\n",
    "            vis.add(start[0]*N+start[1])\n",
    "         \n",
    "            while len(D)>0 and len(vis)<=max_arrive:\n",
    "                cur_x, cur_y = D.popleft()\n",
    "                if [cur_x, cur_y]==ends:\n",
    "                    return True\n",
    "\n",
    "                for x, y in [(cur_x-1, cur_y),(cur_x+1, cur_y),(cur_x, cur_y-1),(cur_x, cur_y+1)]:\n",
    "                    code = x*N+y\n",
    "                    if x<0 or x>=N or y<0 or y>=N or code in vis:\n",
    "                        continue\n",
    "                    if [x,y] in blocked:\n",
    "                        continue\n",
    "                   \n",
    "                    vis.add(code)\n",
    "                    D.append([x,y])\n",
    "            return len(vis)>max_arrive\n",
    "        \n",
    "        res1 = bfs(source, target)\n",
    "        if res1 == False:\n",
    "            return False\n",
    "        \n",
    "        return bfs(target, source)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque\n",
    "\n",
    "class Solution:\n",
    "    def isEscapePossible(self, blocked: List[List[int]], source: List[int], target: List[int]) -> bool:\n",
    "        if len(blocked) < 2:\n",
    "            return True \n",
    "\n",
    "        FOUND, BLOCKED, VALID = 1, -1, 0\n",
    "        BOUND = 10 ** 6\n",
    "        n = len(blocked)      \n",
    "        blockedSet = set(tuple(x) for x in blocked)       \n",
    "\n",
    "        def check(src, dst):\n",
    "            x0, y0 = src\n",
    "            x1, y1 = dst\n",
    "            cnt = n * (n - 1) / 2 + 1\n",
    "\n",
    "            bfs = deque([(x0, y0)])\n",
    "            visited = set([(x0, y0)])\n",
    "\n",
    "            while bfs and cnt > 0:\n",
    "                x, y = bfs.popleft()\n",
    "                for nx, ny in [(x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1)]:\n",
    "                    if 0 <= nx < BOUND and 0 <= ny < BOUND and (nx, ny) not in blockedSet and (nx, ny) not in visited:\n",
    "                        if (nx, ny) == (x1, y1):\n",
    "                            return FOUND\n",
    "                        bfs.append((nx, ny))\n",
    "                        visited.add((nx, ny))\n",
    "                        cnt -= 1\n",
    "            if cnt > 0:\n",
    "                return BLOCKED\n",
    "            return VALID\n",
    "\n",
    "        result = check(source, target)\n",
    "        if result == FOUND:\n",
    "            return True\n",
    "        elif result == BLOCKED:\n",
    "            return False\n",
    "\n",
    "        result = check(target, source)\n",
    "        if result == BLOCKED:\n",
    "            return False\n",
    "        return True "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isEscapePossible(self, blocked: List[List[int]], source: List[int], target: List[int]) -> bool:\n",
    "        BLOCKED, VALID, FOUND = -1, 0, 1\n",
    "        BOUNDARY = 10**6\n",
    "\n",
    "        if len(blocked) < 2:\n",
    "            return True\n",
    "        \n",
    "        hash_blocked = set(tuple(pos) for pos in blocked)\n",
    "\n",
    "        def check(start: List[int], finish: List[int]) -> int:\n",
    "            sx, sy = start\n",
    "            fx, fy = finish\n",
    "            countdown = len(blocked) * (len(blocked) - 1) // 2\n",
    "\n",
    "            q = deque([(sx, sy)])\n",
    "            visited = set([(sx, sy)])\n",
    "\n",
    "            while q and countdown > 0:\n",
    "                x, y = q.popleft()\n",
    "                for nx, ny in [(x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1)]:\n",
    "                    if 0 <= nx < BOUNDARY and 0 <= ny < BOUNDARY and (nx, ny) not in hash_blocked and (nx, ny) not in visited:\n",
    "                        if (nx, ny) == (fx, fy):\n",
    "                            return FOUND\n",
    "                        countdown -= 1\n",
    "                        q.append((nx, ny))\n",
    "                        visited.add((nx, ny))\n",
    "            if countdown > 0:\n",
    "                return BLOCKED\n",
    "            return VALID\n",
    "        if check(source, target) == FOUND:\n",
    "            return True\n",
    "        elif check(source, target) == BLOCKED:\n",
    "            return False\n",
    "        else:\n",
    "            result = check(target, source)\n",
    "            if result == BLOCKED:\n",
    "                return False\n",
    "            return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isEscapePossible(self, blocked: List[List[int]], source: List[int], target: List[int]) -> bool:\n",
    "\n",
    "        \"\"\"\n",
    "        BLOCKED: 在包围圈中\n",
    "        VALID:   不在包围圈中\n",
    "        FOUND:   无论在不在包围圈中，但在 n(n-1)/2 步搜索的过程中经过了 target\n",
    "        \"\"\"\n",
    "        BLOCKED, VALID, FOUND = -1, 0, 1\n",
    "        BOUNDARY = 10**6\n",
    "\n",
    "        if len(blocked) < 2:\n",
    "            return True\n",
    "\n",
    "        hash_blocked = set(tuple(pos) for pos in blocked)\n",
    "\n",
    "        def check(start: List[int], finish: List[int]) -> int:\n",
    "            sx, sy = start\n",
    "            fx, fy = finish\n",
    "            countdown = len(blocked) * (len(blocked) - 1) // 2\n",
    "            \n",
    "            q = deque([(sx, sy)])\n",
    "            visited = set([(sx, sy)])\n",
    "            \n",
    "            while q and countdown > 0:\n",
    "                x, y = q.popleft()\n",
    "                for nx, ny in [(x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1)]:\n",
    "                    if 0 <= nx < BOUNDARY and 0 <= ny < BOUNDARY and (nx, ny) not in hash_blocked and (nx, ny) not in visited:\n",
    "                        if (nx, ny) == (fx, fy):\n",
    "                            return FOUND\n",
    "                        countdown -= 1\n",
    "                        q.append((nx, ny))\n",
    "                        visited.add((nx, ny))\n",
    "            \n",
    "            if countdown > 0:\n",
    "                return BLOCKED\n",
    "            return VALID\n",
    "\n",
    "        if (result := check(source, target)) == FOUND:\n",
    "            return True\n",
    "        elif result == BLOCKED:\n",
    "            return False\n",
    "        else:\n",
    "            result = check(target, source)\n",
    "            if result == BLOCKED:\n",
    "                return False\n",
    "            return True\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isEscapePossible(self, blocked: List[List[int]], source: List[int], target: List[int]) -> bool:\n",
    "        m = len(blocked)\n",
    "        setb = set()\n",
    "        for x, y in blocked:\n",
    "            setb.add((x, y))\n",
    "        def bfs(point, dst):\n",
    "            vis = setb.copy()\n",
    "            sx, sy = point\n",
    "            q = deque()\n",
    "            q.append((sx, sy))\n",
    "            vis.add((sx, sy))\n",
    "            cnt = 1\n",
    "            while q:\n",
    "                x, y = q.popleft()\n",
    "                if x == dst[0] and y == dst[1]: return True\n",
    "                for nx, ny in (x, y + 1), (x + 1, y), (x, y - 1), (x - 1, y):\n",
    "                    if 0 <= nx < 10**6 and 0 <= ny < 10**6 and (nx, ny) not in vis:\n",
    "                        cnt += 1\n",
    "                        if cnt * 2 > m * (m - 1): return True\n",
    "                        q.append((nx, ny))\n",
    "                        vis.add((nx, ny))\n",
    "                        \n",
    "            return False\n",
    "\n",
    "        return bfs(source, target) and bfs(target, source)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isEscapePossible(self, blocked: List[List[int]], source: List[int], target: List[int]) -> bool:\n",
    "        m = len(blocked)\n",
    "        setb = set()\n",
    "        for x, y in blocked:\n",
    "            setb.add((x, y))\n",
    "        def bfs(point, dst):\n",
    "            vis = setb.copy()\n",
    "            sx, sy = point\n",
    "            q = deque()\n",
    "            q.append((sx, sy))\n",
    "            vis.add((sx, sy))\n",
    "            cnt = 1\n",
    "            while q:\n",
    "                x, y = q.popleft()\n",
    "                if x == dst[0] and y == dst[1]: return True\n",
    "                for nx, ny in (x, y + 1), (x + 1, y), (x, y - 1), (x - 1, y):\n",
    "                    if 0 <= nx < 10**6 and 0 <= ny < 10**6 and (nx, ny) not in vis:\n",
    "                        cnt += 1\n",
    "                        if cnt * 2 > m * (m + 1): return True\n",
    "                        q.append((nx, ny))\n",
    "                        vis.add((nx, ny))\n",
    "                        \n",
    "            return False\n",
    "\n",
    "        return bfs(source, target) and bfs(target, source)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque\n",
    "\n",
    "class Solution:\n",
    "    def isEscapePossible(self, blocked: List[List[int]], source: List[int], target: List[int]) -> bool:\n",
    "        if len(blocked) < 2:\n",
    "            return True \n",
    "\n",
    "        FOUND, BLOCKED, VALID = 1, -1, 0\n",
    "        BOUND = 10 ** 6\n",
    "        n = len(blocked)      \n",
    "        blockedSet = set(tuple(x) for x in blocked)       \n",
    "\n",
    "        def check(src, dst):\n",
    "            x0, y0 = src\n",
    "            x1, y1 = dst\n",
    "            cnt = n * (n - 1) / 2\n",
    "\n",
    "            bfs = deque([(x0, y0)])\n",
    "            visited = set([(x0, y0)])\n",
    "\n",
    "            while bfs and cnt > 0:\n",
    "                x, y = bfs.popleft()\n",
    "                for nx, ny in [(x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1)]:\n",
    "                    if 0 <= nx < BOUND and 0 <= ny < BOUND and (nx, ny) not in blockedSet and (nx, ny) not in visited:\n",
    "                        if (nx, ny) == (x1, y1):\n",
    "                            return FOUND\n",
    "                        bfs.append((nx, ny))\n",
    "                        visited.add((nx, ny))\n",
    "                        cnt -= 1\n",
    "            if cnt > 0:\n",
    "                return BLOCKED\n",
    "            return VALID\n",
    "\n",
    "        result = check(source, target)\n",
    "        if result == FOUND:\n",
    "            return True\n",
    "        elif result == BLOCKED:\n",
    "            return False\n",
    "\n",
    "        result = check(target, source)\n",
    "        if result == BLOCKED:\n",
    "            return False\n",
    "        return True "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isEscapePossible(self, blocked: List[List[int]], source: List[int], target: List[int]) -> bool:\n",
    "        \"\"\"\n",
    "        BLOCKED: 在包围圈中\n",
    "        VALID:   不在包围圈中\n",
    "        FOUND:   无论在不在包围圈中，但在 n(n-1)/2 步搜索的过程中经过了 target\n",
    "        \"\"\"\n",
    "        BLOCKED, VALID, FOUND = -1, 0, 1\n",
    "        BOUNDARY = 10**6\n",
    "\n",
    "        if len(blocked) < 2:\n",
    "            return True\n",
    "\n",
    "        hash_blocked = set(tuple(pos) for pos in blocked)\n",
    "\n",
    "        def check(start: List[int], finish: List[int]) -> int:\n",
    "            sx, sy = start\n",
    "            fx, fy = finish\n",
    "            countdown = len(blocked) * (len(blocked) - 1) // 2\n",
    "            \n",
    "            q = deque([(sx, sy)])\n",
    "            visited = set([(sx, sy)])\n",
    "            \n",
    "            while q and countdown > 0:\n",
    "                x, y = q.popleft()\n",
    "                for nx, ny in [(x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1)]:\n",
    "                    if 0 <= nx < BOUNDARY and 0 <= ny < BOUNDARY and (nx, ny) not in hash_blocked and (nx, ny) not in visited:\n",
    "                        if (nx, ny) == (fx, fy):\n",
    "                            return FOUND\n",
    "                        countdown -= 1\n",
    "                        q.append((nx, ny))\n",
    "                        visited.add((nx, ny))\n",
    "            \n",
    "            if countdown > 0:\n",
    "                return BLOCKED\n",
    "            return VALID\n",
    "\n",
    "        if (result := check(source, target)) == FOUND:\n",
    "            return True\n",
    "        elif result == BLOCKED:\n",
    "            return False\n",
    "        else:\n",
    "            result = check(target, source)\n",
    "            if result == BLOCKED:\n",
    "                return False\n",
    "            return True\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isEscapePossible(self, blocked: List[List[int]], source: List[int], target: List[int]) -> bool:\n",
    "        n = int(1e6)\n",
    "\n",
    "        blocked = set((x, y) for x, y in blocked)\n",
    "\n",
    "        if len(blocked) < 2:\n",
    "            return True\n",
    "\n",
    "        def search(source, target):\n",
    "            q = deque([(source[0], source[1])])\n",
    "\n",
    "            visited = set()\n",
    "\n",
    "            m = len(blocked)\n",
    "            limit = ceil((m * (m - 1)) / 2)\n",
    "\n",
    "            while q:\n",
    "                i, j = q.popleft()\n",
    "\n",
    "                if (i, j) not in visited:\n",
    "                    visited.add((i, j))\n",
    "                else:\n",
    "                    continue\n",
    "\n",
    "                if len(visited) > limit:\n",
    "                    return True\n",
    "\n",
    "                if target[0] == i and target[1] == j:\n",
    "                    return True\n",
    "\n",
    "                for a, b in ((i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1)):\n",
    "                    if 0 <= a < n and 0 <= b < n:\n",
    "                        if (a, b) not in blocked and (a, b) not in visited:\n",
    "                            q.append((a, b))\n",
    "\n",
    "            return False\n",
    "\n",
    "        return search(source, target) and search(target, source)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isEscapePossible(self, blocked: List[List[int]], source: List[int], target: List[int]) -> bool:\n",
    "        lstblk, tmpb = list(map(tuple, blocked)), len(blocked) ** 2 >> 1\n",
    "        def func(source, target):\n",
    "            se, se_, se1 = {tuple(source)}, set(), {tuple(source)}\n",
    "            while se:\n",
    "                for x, y in se:\n",
    "                    for x_, y_ in (x - 1, y), (x, y - 1), (x, y + 1), (x + 1, y): \n",
    "                        if [x_, y_] == target: return True\n",
    "                        if 0 <= x_ < 1000000 and 0 <= y_ < 1000000 and (x_, y_) not in se1 and (x_, y_) not in lstblk:\n",
    "                            se_.add((x_, y_))\n",
    "                            se1.add((x_, y_))\n",
    "                if len(se1) > tmpb : return True\n",
    "                se, se_ = se_, set()\n",
    "            return False\n",
    "        return func(source, target) and func(target, source) \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isEscapePossible(self, blocked, source, target) -> bool:\n",
    "        \"\"\"\n",
    "        题目要求：题目本身其实很简单，就是在一个足够大的棋盘里，存在少量障碍物，判断起始两点是否能够连通\n",
    "        :param blocked: 障碍物的坐标列表\n",
    "        :param source: 起始点坐标\n",
    "        :param target: 终止点坐标\n",
    "        :return: 返回True/False\n",
    "        \"\"\"\n",
    "        # 解题思路：此题的背景超级常见，在一个二维表中的搜索问题(本质就是图遍历的一种，主流的两种方法，深度优先BFS和广度优先DFS)，每次只能向上下左右四个方向移动\n",
    "        # 广度优先一般使用队列实现，深度优先一般使用递归或栈来实现(有固定套路的，可以去了解，这是基础知识)\n",
    "        # 所以这个题总体思路及其简单，就是通过起始点搜索看能否找到终止点(障碍不能过)，该题的主要难点在于这个棋盘非常大，常规的遍历搜索可能会搜完整个棋盘，导致超时\n",
    "        # 故该题要考虑如何在有限步的搜索中，判断出两个点是否可以连通，本解法采用BFS(更易理解，DFS也可以做)\n",
    "        # 进一步分析可知，当两个点中的任意一点被障碍物围住时，两点将必无法连通(逆向思维，找到一定无法连通的可能，剩余情况一定可以连通)\n",
    "        # 那么必无法连通的可能就只有两种：source被障碍完全包围，并且target不在包围圈中；target被障碍完全包围，并且source不在包围圈中。\n",
    "        # 因此就可以形成一个思路：从起始点跑一遍BFS，然后从终止点跑一遍 BFS，同时设定一个最大搜索数量MAX，若从两者出发能够访问的点数量都能超过MAX，说明两点均没有被围住，最终必然会联通\n",
    "        # 现在就是如何设置最大搜索数量MAX，若是简单粗暴一点，可以将MAX设为10**5，这样不会超时，但是效率不高，且该题需要的推理过程，不过这个做法完全可以\n",
    "        # 最大搜索数量MAX就是障碍物能围成的最大面积，可以考虑最差的情况，利用棋盘边界作为两条边(此时相当于将边界也看作的障碍物，是最坏情况)，障碍物提供斜边的直角三角形(品一品)\n",
    "        # 这种情况就好像是利用障碍物连成的一条斜边，切掉了棋盘的一个角，切下的角就是包围圈\n",
    "        # 这个包围圈包含多少个点，就是最大搜索数量MAX。这个不难计算，自己随手画个图很容易看出来，MAX=1+2+3+..+n-1 = n*(n-1)/2 (n为障碍物数量)\n",
    "        if len(blocked) <= 1:  # 障碍物不超过1个，无法形成包围圈，一定可以连通\n",
    "            return True\n",
    "        # 障碍物集合，将每个点坐标转化为元组，存在集合里，比直接访问列表快，节省时间(本题的坑不就是时间问题么)\n",
    "        # 当然直接用原列表也可以，你可以看看时间是不是有差距(就是直接传blocked，不传这个is_blocked)\n",
    "        is_blocked = {tuple(pos) for pos in blocked}\n",
    "        MAX = len(blocked) * (len(blocked) - 1) // 2  # 这是精细分析的设置\n",
    "        # MAX = 10 ** 5 # 这是粗暴的设置\n",
    "        # BFS判断两点是否被包围，均没有被围住必连通\n",
    "        return self.BFS(source, target, is_blocked, MAX) and self.BFS(target, source, is_blocked, MAX)\n",
    "\n",
    "\n",
    "    def BFS(self, source, target, is_blocked, MAX) -> bool:\n",
    "        \"\"\"\n",
    "        广度优先搜索，判断两点是否被包围\n",
    "        :param source: 起始点坐标\n",
    "        :param target: 终止点坐标\n",
    "        :param is_blocked: 障碍物坐标集合\n",
    "        :param MAX: 最大搜索数量\n",
    "        :return: 返回True/False\n",
    "        \"\"\"\n",
    "        # 取出两个点的坐标，后面使用\n",
    "        sx, sy = source\n",
    "        fx, fy = target\n",
    "        q = deque([(sx, sy)])  # 初始化队列，并将起点入队\n",
    "        visited = {(sx, sy)}  # 设置标记集合，用于标记该点是否访问过，避免重复访问，节省时间，初始时起始点进集合\n",
    "        # 队列不为空且没有超过最大搜索数量，就循环\n",
    "        while q and MAX >= 0:\n",
    "            x, y = q.popleft()  # 将队头点取出\n",
    "            if (x, y) == (fx, fy):  # 如果该点就是终点，找到了，太好了，直接True\n",
    "                return True\n",
    "            # 否则就从该点上下左右依次进行搜索\n",
    "            for nx, ny in [(x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1)]:\n",
    "                # 搜索的点必须不超过边界，且不是障碍物，且没被访问过\n",
    "                if 0 <= nx < 10 ** 6 and 0 <= ny < 10 ** 6 and (nx, ny) not in is_blocked and (nx, ny) not in visited:\n",
    "                    if (nx, ny) == (fx, fy):  # 找到终点了，返回True\n",
    "                        return True\n",
    "                    q.append((nx, ny))  # 将这个点入队，方便后面搜索它的上下左右\n",
    "                    visited.add((nx, ny))  # 标记被访问过\n",
    "                    MAX -= 1  # 最大搜索量减一\n",
    "        return MAX < 0  # 搜索完后且没提前找到，判断最大数量是否用完了，小于0(即访问过的点超过了最大数量)则必没被包围，可以连通；否则就是在包围圈，两个点被隔开了\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque\n",
    "\n",
    "class Solution:\n",
    "    def can_reach_or_step(self, source, target, max_step, blocked):\n",
    "        visited = set(tuple(x) for x in blocked)\n",
    "        visited.add(tuple(source))\n",
    "\n",
    "        max_xy = 10 ** 6\n",
    "\n",
    "        queue = deque()\n",
    "        queue.append(source)\n",
    "        actions = [(-1, 0), (0, -1), (0, 1), (1, 0)]\n",
    "\n",
    "        while queue and max_step >= 0:\n",
    "            currentx, currenty = queue.popleft()\n",
    "            for actionx, actiony in actions:\n",
    "                newx = currentx + actionx\n",
    "                newy = currenty + actiony\n",
    "                if 0 <= newx < max_xy and 0 <= newy < max_xy:\n",
    "                    if newx == target[0] and newy == target[1]:\n",
    "                        return True\n",
    "                    new_pos = (newx, newy)\n",
    "                    if new_pos not in visited:\n",
    "                        queue.append(new_pos)\n",
    "                        visited.add(new_pos)\n",
    "                        max_step -= 1\n",
    "        return max_step < 0\n",
    "\n",
    "    def isEscapePossible(self, blocked: List[List[int]], source: List[int], target: List[int]) -> bool:\n",
    "        n = len(blocked)\n",
    "        max_step = (n ** 2 - n) // 2\n",
    "\n",
    "        rst1 = self.can_reach_or_step(source, target, max_step, blocked)\n",
    "        if not rst1:\n",
    "            return False\n",
    "\n",
    "        rst2 = self.can_reach_or_step(target, source, max_step, blocked)\n",
    "        return rst2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bfs(self, source, target):\n",
    "        sx, sy = source\n",
    "        tx, ty = target\n",
    "        queue = [source]\n",
    "        visited = {(sx, sy)}\n",
    "        valid = 1\n",
    "        while queue and valid <= self.MAXVALID:\n",
    "            x, y = queue.pop(0)\n",
    "            for xx, yy in [[0,1],[0,-1],[1,0],[-1,0]]:\n",
    "                i, j = x + xx, y + yy\n",
    "                if 0 <= i < self.boundary and 0 <= j < self.boundary \\\n",
    "                  and [i,j] not in self.blocked and (i,j) not in visited:\n",
    "                    if i == tx and j == ty:\n",
    "                        return self.FOUND\n",
    "                    queue.append([i,j])\n",
    "                    visited.add((i,j))\n",
    "                    valid += 1\n",
    "\n",
    "        if valid <= self.MAXVALID:\n",
    "            return self.BLOCKED\n",
    "        return self.VALILD\n",
    "\n",
    "    def isEscapePossible(self, blocked: List[List[int]], source: List[int], target: List[int]) -> bool:\n",
    "        n = len(blocked)\n",
    "        self.FOUND, self.VALILD, self.BLOCKED = 0, 1, -1\n",
    "        self.boundary = 10 ** 6\n",
    "        self.MAXVALID = ((n - 1) * n) // 2\n",
    "        self.blocked = blocked\n",
    "        res = self.bfs(source, target)\n",
    "        if res == self.FOUND:\n",
    "            return True\n",
    "        elif res == self.BLOCKED:\n",
    "            return False\n",
    "        else:\n",
    "            res = self.bfs(target, source)\n",
    "            if res == self.BLOCKED:\n",
    "                return False\n",
    "            return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isEscapePossible(self, blocked: List[List[int]], source: List[int], target: List[int]) -> bool:\n",
    "        \n",
    "        direction = [[0,1],[1,0],[0,-1],[-1,0]]\n",
    "        N = 10 ** 6\n",
    "        for i in range(len(blocked)):\n",
    "            blocked[i] = tuple(blocked[i])\n",
    "\n",
    "        def bfs(source,target):\n",
    "            queue = deque([source])\n",
    "            visited = set()\n",
    "            visited.add(source)\n",
    "            while queue:\n",
    "                i , j = queue.popleft()\n",
    "                if (i,j) == target or len(visited) > t:\n",
    "                    return True\n",
    "                for di , dj in direction:\n",
    "                    ni , nj = i + di , j + dj\n",
    "                    if 0 <= ni < N and 0 <= nj < N and (ni,nj) not in visited and (ni,nj) not in blocked:\n",
    "                        visited.add((ni,nj))\n",
    "                        queue.append((ni,nj))\n",
    "            return False\n",
    "\n",
    "        n = len(blocked)\n",
    "        t = n*(n-1)//2\n",
    "        source = tuple(source)\n",
    "        target = tuple(target)\n",
    "\n",
    "        if bfs(source,target) and bfs(target,source):\n",
    "            return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isEscapePossible(self, blocked: List[List[int]], source: List[int], target: List[int]) -> bool:\n",
    "        m = len(blocked)\n",
    "        blocked, limit = [tuple(p) for p in blocked], m * (m - 1) // 2\n",
    "\n",
    "        def bfs(st, ed):\n",
    "            q = deque([tuple(st)])\n",
    "            vis = {tuple(st)}\n",
    "            cnt = 1\n",
    "            while q:\n",
    "                x, y = q.popleft()\n",
    "                if cnt > limit or x == ed[0] and y == ed[1]: return True\n",
    "                for dx, dy in pairwise([-1, 0, 1, 0, -1]):\n",
    "                    nx, ny = x + dx, y + dy\n",
    "                    if 0 <= nx < 10 ** 6 and 0 <= ny < 10 ** 6 and (nx, ny) not in blocked and (nx, ny) not in vis:\n",
    "                        q.append((nx, ny))\n",
    "                        vis.add((nx, ny))\n",
    "                        cnt += 1\n",
    "            return False\n",
    "        return bfs(source, target) and bfs(target, source)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isEscapePossible(self, blocked: List[List[int]], source: List[int], target: List[int]) -> bool:\n",
    "        blocked = set(tuple(b) for b in blocked)\n",
    "        n = len(blocked)\n",
    "        maxstep = n * (n + 1) // 2\n",
    "        def dfs(sr, dt):\n",
    "            visit = set()\n",
    "            queue = collections.deque([sr])\n",
    "            while queue:\n",
    "                i, j = queue.popleft() \n",
    "                if (i, j) == dt:\n",
    "                    return True \n",
    "                if len(visit) >= maxstep:\n",
    "                    return True \n",
    "                for d in ((-1, 0), (0, -1), (1, 0), (0, 1)):\n",
    "                    x = i + d[0]\n",
    "                    y = j + d[1]\n",
    "                    if 0 <= x < 10 ** 6 and 0 <= y < 10 ** 6 and (x, y) not in visit and (x, y) not in blocked:\n",
    "                        visit.add((x, y))\n",
    "                        queue.append((x, y))\n",
    "            return False \n",
    "        source = tuple(source)\n",
    "        target = tuple(target)\n",
    "        return dfs(source, target) and dfs(target, source)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isEscapePossible(self, blocked: List[List[int]], source: List[int], target: List[int]) -> bool:\n",
    "        nb = len(blocked)\n",
    "        max_step = nb ** 2 // 2\n",
    "        source, target = (source[0], source[1]), (target[0], target[1])\n",
    "        is_reach = {source}\n",
    "        block_set = {(x[0], x[1]) for x in blocked}\n",
    "        queue, head = [source], 0\n",
    "        while head < len(queue) and len(queue) < max_step:\n",
    "            if (target[0], target[1]) in is_reach:\n",
    "                return True\n",
    "            x0, y0 = queue[head]\n",
    "            head += 1\n",
    "            for x, y in [(x0 - 1, y0), (x0 + 1, y0), (x0, y0 - 1), (x0, y0 + 1)]:\n",
    "                if x >= 0 and x < 10 ** 6 and y >= 0 and y < 10 ** 6 and (x, y) not in block_set and (x, y) not in is_reach:\n",
    "                    queue.append((x, y))\n",
    "                    is_reach.add((x, y))\n",
    "        \n",
    "        if len(queue) < max_step: return False\n",
    "\n",
    "        is_reach = {target}\n",
    "        block_set = {(x[0], x[1]) for x in blocked}\n",
    "        queue, head = [target], 0\n",
    "        while head < len(queue) and len(queue) < max_step:\n",
    "            if source in queue:\n",
    "                return True\n",
    "            x0, y0 = queue[head]\n",
    "            head += 1\n",
    "            for x, y in [(x0 - 1, y0), (x0 + 1, y0), (x0, y0 - 1), (x0, y0 + 1)]:\n",
    "                if x >= 0 and x < 10 ** 6 and y >= 0 and y < 10 ** 6 and (x, y) not in block_set and (x, y) not in is_reach:\n",
    "                    queue.append((x, y))\n",
    "                    is_reach.add((x, y))\n",
    "        \n",
    "        return len(queue) >= max_step\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isEscapePossible(self, blocked: List[List[int]], source: List[int], target: List[int]) -> bool:\n",
    "        nb = len(blocked)\n",
    "        max_step = nb ** 2 // 2\n",
    "        dirs = [(0, 1), (0, -1), (-1, 0), (1, 0)]\n",
    "        source, target = (source[0], source[1]), (target[0], target[1])\n",
    "        is_reach = {source}\n",
    "        block_set = {(x[0], x[1]) for x in blocked}\n",
    "        queue, head = [source], 0\n",
    "        while head < len(queue) and len(queue) < max_step:\n",
    "            if (target[0], target[1]) in is_reach:\n",
    "                return True\n",
    "            x0, y0 = queue[head]\n",
    "            head += 1\n",
    "            for x, y in [(x0 - 1, y0), (x0 + 1, y0), (x0, y0 - 1), (x0, y0 + 1)]:\n",
    "                if x >= 0 and x < 10 ** 6 and y >= 0 and y < 10 ** 6 and (x, y) not in block_set and (x, y) not in is_reach:\n",
    "                    queue.append((x, y))\n",
    "                    is_reach.add((x, y))\n",
    "        \n",
    "        if len(queue) < max_step: return False\n",
    "\n",
    "        is_reach = {target}\n",
    "        block_set = {(x[0], x[1]) for x in blocked}\n",
    "        queue, head = [target], 0\n",
    "        while head < len(queue) and len(queue) < max_step:\n",
    "            if source in queue:\n",
    "                return True\n",
    "            x0, y0 = queue[head]\n",
    "            head += 1\n",
    "            for x, y in [(x0 - 1, y0), (x0 + 1, y0), (x0, y0 - 1), (x0, y0 + 1)]:\n",
    "                if x >= 0 and x < 10 ** 6 and y >= 0 and y < 10 ** 6 and (x, y) not in block_set and (x, y) not in is_reach:\n",
    "                    queue.append((x, y))\n",
    "                    is_reach.add((x, y))\n",
    "        \n",
    "        return len(queue) >= max_step\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isEscapePossible(self, blocked: List[List[int]], source: List[int], target: List[int]) -> bool:\n",
    "        nb = len(blocked)\n",
    "        max_step = nb ** 2 // 2\n",
    "        source, target = (source[0], source[1]), (target[0], target[1])\n",
    "        is_reach = {source}\n",
    "        block_set = {(x[0], x[1]) for x in blocked}\n",
    "        queue, head = [source], 0\n",
    "        while head < len(queue) and len(queue) < max_step:\n",
    "            if queue[head] == target: return True\n",
    "            x0, y0 = queue[head]\n",
    "            head += 1\n",
    "            for x, y in [(x0 - 1, y0), (x0 + 1, y0), (x0, y0 - 1), (x0, y0 + 1)]:\n",
    "                if 0 <= x < 1000000 and 0 <= y < 1000000 and (x, y) not in block_set and (x, y) not in is_reach:\n",
    "                    queue.append((x, y))\n",
    "                    is_reach.add((x, y))\n",
    "        \n",
    "        if len(queue) < max_step: return False\n",
    "\n",
    "        is_reach = {target}\n",
    "        block_set = {(x[0], x[1]) for x in blocked}\n",
    "        queue, head = [target], 0\n",
    "        while head < len(queue) and len(queue) < max_step:\n",
    "            if queue[head] == source: return True\n",
    "            x0, y0 = queue[head]\n",
    "            head += 1\n",
    "            for x, y in [(x0 - 1, y0), (x0 + 1, y0), (x0, y0 - 1), (x0, y0 + 1)]:\n",
    "                if 0 <= x < 1000000 and 0 <= y < 1000000 and (x, y) not in block_set and (x, y) not in is_reach:\n",
    "                    queue.append((x, y))\n",
    "                    is_reach.add((x, y))\n",
    "        \n",
    "        return len(queue) >= max_step"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isEscapePossible(self, blocked: List[List[int]], source: List[int], target: List[int]) -> bool:\n",
    "        nb = len(blocked)\n",
    "        max_step = nb ** 2 // 2\n",
    "        source, target = (source[0], source[1]), (target[0], target[1])\n",
    "        is_reach = {source}\n",
    "        block_set = {(x[0], x[1]) for x in blocked}\n",
    "        queue, head = [source], 0\n",
    "        while head < len(queue) and len(queue) < max_step:\n",
    "            if (target[0], target[1]) in is_reach:\n",
    "                return True\n",
    "            x0, y0 = queue[head]\n",
    "            head += 1\n",
    "            for x, y in [(x0 - 1, y0), (x0 + 1, y0), (x0, y0 - 1), (x0, y0 + 1)]:\n",
    "                if 0 <= x < 1000000 and 0 <= y < 1000000 and (x, y) not in block_set and (x, y) not in is_reach:\n",
    "                    queue.append((x, y))\n",
    "                    is_reach.add((x, y))\n",
    "        \n",
    "        if len(queue) < max_step: return False\n",
    "\n",
    "        is_reach = {target}\n",
    "        block_set = {(x[0], x[1]) for x in blocked}\n",
    "        queue, head = [target], 0\n",
    "        while head < len(queue) and len(queue) < max_step:\n",
    "            if source in queue:\n",
    "                return True\n",
    "            x0, y0 = queue[head]\n",
    "            head += 1\n",
    "            for x, y in [(x0 - 1, y0), (x0 + 1, y0), (x0, y0 - 1), (x0, y0 + 1)]:\n",
    "                if 0 <= x < 1000000 and 0 <= y < 1000000 and (x, y) not in block_set and (x, y) not in is_reach:\n",
    "                    queue.append((x, y))\n",
    "                    is_reach.add((x, y))\n",
    "        \n",
    "        return len(queue) >= max_step\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isEscapePossible(self, blocked: List[List[int]], source: List[int], target: List[int]) -> bool:\n",
    "        nb = len(blocked)\n",
    "        max_step = nb ** 2 // 2\n",
    "        dirs = [(0, 1), (0, -1), (-1, 0), (1, 0)]\n",
    "        source, target = (source[0], source[1]), (target[0], target[1])\n",
    "        is_reach = {source}\n",
    "        block_set = {(x[0], x[1]) for x in blocked}\n",
    "        queue, head = [source], 0\n",
    "        while head < len(queue) and len(queue) < max_step:\n",
    "            if (target[0], target[1]) in is_reach:\n",
    "                return True\n",
    "            x0, y0 = queue[head]\n",
    "            head += 1\n",
    "            for dx, dy in dirs:\n",
    "                x, y = x0 + dx, y0 + dy\n",
    "                if x >= 0 and x < 10 ** 6 and y >= 0 and y < 10 ** 6 and (x, y) not in block_set and (x, y) not in is_reach:\n",
    "                    queue.append((x, y))\n",
    "                    is_reach.add((x, y))\n",
    "        \n",
    "        if len(queue) < max_step: return False\n",
    "\n",
    "        is_reach = {target}\n",
    "        block_set = {(x[0], x[1]) for x in blocked}\n",
    "        queue, head = [target], 0\n",
    "        while head < len(queue) and len(queue) < max_step:\n",
    "            if source in queue:\n",
    "                return True\n",
    "            x0, y0 = queue[head]\n",
    "            head += 1\n",
    "            for dx, dy in dirs:\n",
    "                x, y = x0 + dx, y0 + dy\n",
    "                if x >= 0 and x < 10 ** 6 and y >= 0 and y < 10 ** 6 and (x, y) not in block_set and (x, y) not in is_reach:\n",
    "                    queue.append((x, y))\n",
    "                    is_reach.add((x, y))\n",
    "        \n",
    "        return len(queue) >= max_step\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isEscapePossible(self, blocked: List[List[int]], source: List[int], target: List[int]) -> bool:\n",
    "        if not blocked:\n",
    "            return True\n",
    "        \n",
    "        cnt=0\n",
    "\n",
    "        stack=collections.deque()\n",
    "        vis=set()\n",
    "        stack.append(source)\n",
    "        while stack and cnt<40000:\n",
    "            x,y =stack.popleft()\n",
    "            if (x,y) in vis:\n",
    "                continue\n",
    "            vis.add((x,y))\n",
    "            if [x,y]==target:\n",
    "                return True\n",
    "            cnt+=1\n",
    "            for x1,y1 in [[x+1,y],[x-1,y],[x,y+1],[x,y-1]]:\n",
    "                if 0<=x1<1000000 and 0<=y1<1000000 and (x1,y1) not in vis and [x1,y1] not in blocked:\n",
    "                    stack.append([x1,y1]) \n",
    "        if cnt!=40000:\n",
    "            return False\n",
    "        cnt=0\n",
    "        stack=collections.deque()\n",
    "        vis=set()\n",
    "        stack.append(target)\n",
    "        while stack and cnt<40000:\n",
    "            x,y =stack.popleft()\n",
    "            if (x,y) in vis:\n",
    "                continue\n",
    "            vis.add((x,y))\n",
    "            if [x,y]==source:\n",
    "                return True\n",
    "            cnt+=1\n",
    "            for x1,y1 in [[x+1,y],[x-1,y],[x,y+1],[x,y-1]]:\n",
    "                if 0<=x1<1000000 and 0<=y1<1000000 and (x1,y1) not in vis and [x1,y1] not in blocked:\n",
    "                    stack.append([x1,y1]) \n",
    "        if cnt!=40000:\n",
    "            return False\n",
    "        return True\n",
    "        \n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "BOUND = int(1e6)\n",
    "class Solution:\n",
    "    def isEscapePossible(self, blocked: List[List[int]], source: List[int], target: List[int]) -> bool:\n",
    "        blocked, MAX = {tuple(p) for p in blocked}, len(blocked) * (len(blocked) - 1) // 2\n",
    "\n",
    "        def bfs(start, end):\n",
    "            points,idx,explored = [start], 0, {tuple(start)}\n",
    "            while idx < len(points):\n",
    "                for dx, dy in (0, 1), (1,0),(-1,0),(0, -1):\n",
    "                    nx, ny = points[idx][0] + dx, points[idx][1] + dy\n",
    "                    if 0 <= nx < BOUND and 0 <= ny < BOUND and (nx, ny) not in blocked and (nx, ny) not in explored:\n",
    "                        if [nx, ny] == end:\n",
    "                            return True\n",
    "                        explored.add((nx, ny))\n",
    "                        points.append((nx, ny))\n",
    "                if len(points) > MAX:\n",
    "                    return True\n",
    "                idx += 1\n",
    "            return False\n",
    "        \n",
    "        return bfs(source, target) and bfs(target, source)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "BOUND = int(1e6)\n",
    "class Solution:\n",
    "    def isEscapePossible(self, blocked: List[List[int]], source: List[int], target: List[int]) -> bool:\n",
    "        blocked, MAX = {tuple(p) for p in blocked}, len(blocked) * (len(blocked) - 1) // 2\n",
    "\n",
    "        def bfs(start, end):\n",
    "            points,idx,explored = [start], 0, {tuple(start)}\n",
    "            while idx < len(points):\n",
    "                for dx, dy in (0, 1), (1,0),(-1,0),(0, -1):\n",
    "                    nx, ny = points[idx][0] + dx, points[idx][1] + dy\n",
    "                    if 0 <= nx < BOUND and 0 <= ny < BOUND and (nx, ny) not in blocked and (nx, ny) not in explored:\n",
    "                        if [nx, ny] == end:\n",
    "                            return True\n",
    "                        explored.add((nx, ny))\n",
    "                        points.append((nx, ny))\n",
    "                if len(points) > MAX:\n",
    "                    return True\n",
    "                idx += 1\n",
    "            return False\n",
    "        \n",
    "        return bfs(source, target) and bfs(target, source)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque\n",
    "\n",
    "class Solution:\n",
    "    def isEscapePossible(self, blocked: List[List[int]], source: List[int], target: List[int]) -> bool:\n",
    "        blocked = {tuple(p) for p in blocked}\n",
    "        directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]\n",
    "        \n",
    "        def bfs(source, target):\n",
    "            bfs, seen = [source], {tuple(source)}\n",
    "            for x0, y0 in bfs:\n",
    "                for dx, dy in directions:\n",
    "                    x, y = x0 + dx, y0 + dy\n",
    "                    if 0 <= x < 10**6 and 0 <= y < 10**6 and (x, y) not in seen and (x, y) not in blocked:\n",
    "                        if (x, y) == tuple(target): return True\n",
    "                        bfs.append((x, y))\n",
    "                        seen.add((x, y))\n",
    "                if len(bfs) == 20000: return True\n",
    "            return False\n",
    "        \n",
    "        return bfs(source, target) and bfs(target, source)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isEscapePossible(self, b: List[List[int]], source: List[int], target: List[int]) -> bool:\n",
    "        n = len(b)\n",
    "        m = n*n\n",
    "        b = {(x, y) for x, y in b}\n",
    "        a = [[1, 0], [-1, 0], [0, 1], [0, -1]]\n",
    "        end = tuple(target)\n",
    "        i, j  = source\n",
    "        s = [(i, j)]\n",
    "        v = {(i, j)}\n",
    "        num = 1\n",
    "        while s:\n",
    "            tmp = []\n",
    "            for x, y in s:\n",
    "                for i, j in a:\n",
    "                    i+=x\n",
    "                    j+=y\n",
    "                    if (0<=i<10**6) and (0<=j<10**6):\n",
    "                        if (i, j) not in v:\n",
    "                            if (i, j) not in b:\n",
    "                                v.add((i, j))\n",
    "                                tmp.append((i, j))\n",
    "            s = tmp \n",
    "            num+=len(s) \n",
    "            if end in v:\n",
    "                return True \n",
    "            if num>m:\n",
    "                break \n",
    "        if num<=m:\n",
    "            return False \n",
    "\n",
    "        end = tuple(source)\n",
    "        i, j  = target\n",
    "        s = [(i, j)]\n",
    "        v = {(i, j)}\n",
    "        num = 1\n",
    "        while s:\n",
    "            tmp = []\n",
    "            for x, y in s:\n",
    "                for i, j in a:\n",
    "                    i+=x\n",
    "                    j+=y\n",
    "                    if (0<=i<10**6) and (0<=j<10**6):\n",
    "                        if (i, j) not in v:\n",
    "                            if (i, j) not in b:\n",
    "                                v.add((i, j))\n",
    "                                tmp.append((i, j))\n",
    "            s = tmp \n",
    "            num+=len(s) \n",
    "            # if end in v:\n",
    "            #     return True \n",
    "            if num>m:\n",
    "                break \n",
    "        if num<=m:\n",
    "            return False \n",
    "        return True \n",
    "        \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isEscapePossible(self, blocked: List[List[int]], source: List[int], target: List[int]) -> bool:\n",
    "        if not blocked:\n",
    "            return True\n",
    "        d=[[0,1],[1,0],[0,-1],[-1,0]]\n",
    "        block=set()\n",
    "        for a,b in blocked:\n",
    "            block.add((a,b))\n",
    "        c=0\n",
    "        q=collections.deque()\n",
    "        find=set()\n",
    "        find.add(tuple(source))\n",
    "        q.append(tuple(source))\n",
    "        while q and c<40000:\n",
    "            \n",
    "            x,y=q.popleft()\n",
    "            #if c<100:\n",
    "            #    print(x,y)\n",
    "            #print(x,y)\n",
    "            if [x,y]==target:\n",
    "                return True\n",
    "            #if (x,y) in find:\n",
    "            #    continue\n",
    "            c+=1\n",
    "            for dx,dy in d:\n",
    "                xx,yy=x+dx,y+dy\n",
    "                #print(xx,yy)\n",
    "                if 999999>=xx>=0 and 999999>=yy>=0 and  (xx,yy) not in block and (xx,yy) not in find:\n",
    "                    q.append((xx,yy))\n",
    "                    find.add((xx,yy))\n",
    "        print(c)\n",
    "        if c!=40000:\n",
    "            return False\n",
    "        c=0\n",
    "        q=collections.deque()\n",
    "        find=set()\n",
    "        find.add(tuple(target))\n",
    "        q.append(tuple(target))\n",
    "        while q and c<40000:\n",
    "            x,y=q.popleft()\n",
    "            #if (x,y) in find:\n",
    "            #    continue\n",
    "            c+=1\n",
    "            for dx,dy in d:\n",
    "                xx,yy=x+dx,y+dy\n",
    "                if xx>0 and yy>0 and  (xx,yy) not in block and (xx,yy) not in find:\n",
    "                    q.append((xx,yy))\n",
    "                    find.add((xx,yy))\n",
    "        print(c)\n",
    "        if c!=40000:\n",
    "            return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isEscapePossible(self, blocked: List[List[int]], source: List[int], target: List[int]) -> bool:\n",
    "        if not blocked:\n",
    "            return True\n",
    "        d=[[0,1],[1,0],[0,-1],[-1,0]]\n",
    "        block=set()\n",
    "        for a,b in blocked:\n",
    "            block.add((a,b))\n",
    "        c=0\n",
    "        q=collections.deque()\n",
    "        find=set()\n",
    "        find.add(tuple(source))\n",
    "        q.append(tuple(source))\n",
    "        while q and c<40000:\n",
    "            \n",
    "            x,y=q.popleft()\n",
    "            if c<100:\n",
    "                print(x,y)\n",
    "            #print(x,y)\n",
    "            if [x,y]==target:\n",
    "                return True\n",
    "            #if (x,y) in find:\n",
    "            #    continue\n",
    "            c+=1\n",
    "            for dx,dy in d:\n",
    "                xx,yy=x+dx,y+dy\n",
    "                #print(xx,yy)\n",
    "                if 999999>=xx>=0 and 999999>=yy>=0 and  (xx,yy) not in block and (xx,yy) not in find:\n",
    "                    q.append((xx,yy))\n",
    "                    find.add((xx,yy))\n",
    "        print(c)\n",
    "        if c!=40000:\n",
    "            return False\n",
    "        c=0\n",
    "        q=collections.deque()\n",
    "        find=set()\n",
    "        find.add(tuple(target))\n",
    "        q.append(tuple(target))\n",
    "        while q and c<40000:\n",
    "            x,y=q.popleft()\n",
    "            #if (x,y) in find:\n",
    "            #    continue\n",
    "            c+=1\n",
    "            for dx,dy in d:\n",
    "                xx,yy=x+dx,y+dy\n",
    "                if xx>0 and yy>0 and  (xx,yy) not in block and (xx,yy) not in find:\n",
    "                    q.append((xx,yy))\n",
    "                    find.add((xx,yy))\n",
    "        print(c)\n",
    "        if c!=40000:\n",
    "            return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isEscapePossible(self, blocked: List[List[int]], source: List[int], target: List[int]) -> bool:\n",
    "        n = len(blocked)\n",
    "        dic = set(map(tuple, blocked))\n",
    "        MAXNUM = n*(n-1)//2\n",
    "        seen1 = set([tuple(source)])\n",
    "        q = deque([tuple(source)])\n",
    "        cnt = 0\n",
    "        while q and cnt <= MAXNUM:\n",
    "            x, y = q.popleft()\n",
    "            cnt += 1\n",
    "            for a, b in [(x-1, y), (x+1, y), (x, y+1), (x, y-1)]:\n",
    "                if 0 <= a < 1000000 and 0 <= b < 1000000 and (a, b) not in seen1 and (a, b) not in dic:\n",
    "                    q.append((a, b))\n",
    "                    seen1.add((a, b))\n",
    "        flag = (cnt > MAXNUM)\n",
    "\n",
    "        seen2 = set([tuple(target)])\n",
    "        q = deque([tuple(target)])\n",
    "        cnt = 0\n",
    "        while q and cnt <= MAXNUM:\n",
    "            x, y = q.popleft()\n",
    "            cnt += 1\n",
    "            if (x, y) in seen1:\n",
    "                return True\n",
    "            for a, b in [(x-1, y), (x+1, y), (x, y+1), (x, y-1)]:\n",
    "                if 0 <= a < 1000000 and 0 <= b < 1000000 and (a, b) not in seen2 and (a, b) not in dic:\n",
    "                    q.append((a, b))\n",
    "                    seen2.add((a, b))\n",
    "        if flag and cnt > MAXNUM:\n",
    "            return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isEscapePossible(self, blocked: List[List[int]], source: List[int], target: List[int]) -> bool:\n",
    "        blocked = set((x, y) for x, y in blocked)\n",
    "        def check_escape(s, t, lim):\n",
    "            sx, sy = s\n",
    "            tx, ty = t\n",
    "            vis = set([(sx, sy)])\n",
    "            queue = deque([(sx, sy)])\n",
    "            while len(queue) > 0:\n",
    "                cx, cy = queue.popleft()\n",
    "                for nx, ny in [(cx - 1, cy), (cx + 1, cy), (cx, cy - 1), (cx, cy + 1)]:\n",
    "                    if 0 <= nx < 10 ** 6 and 0 <= ny < 10 ** 6 and (nx, ny) not in vis and (nx, ny) not in blocked:           \n",
    "                        if (nx, ny) == (tx, ty):\n",
    "                            return 2\n",
    "                        if nx < sx - lim or nx > sx + lim or ny < sy - lim or ny > sy + lim:\n",
    "                            return 1\n",
    "                        vis.add((nx, ny))\n",
    "                        queue.append((nx, ny))\n",
    "            return 0\n",
    "        \n",
    "        state_1 = check_escape(source, target, len(blocked))\n",
    "        if state_1 == 2:\n",
    "            return True\n",
    "        elif state_1 == 0:\n",
    "            return False\n",
    "        state_2 = check_escape(target, source, len(blocked))\n",
    "        if state_2 == 2:\n",
    "            return True\n",
    "        elif state_2 == 0:\n",
    "            return False\n",
    "        return True\n",
    "        \n",
    "                        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isEscapePossible(self, blocked: List[List[int]], source: List[int], target: List[int]) -> bool:\n",
    "        n = int(1e6)\n",
    "\n",
    "        blocked = set((x, y) for x, y in blocked)\n",
    "\n",
    "        if len(blocked) < 2:\n",
    "            return True\n",
    "\n",
    "        def h(i, j):\n",
    "            return 2 * (abs(target[0] - i) + abs(target[1] - j))\n",
    "\n",
    "        def search(source, target):\n",
    "            q = [(h(source[0], source[0]), 0, source[0], source[1])]\n",
    "\n",
    "            visited = set()\n",
    "\n",
    "            m = len(blocked)\n",
    "            limit = ceil((m * (m - 1)) / 2)\n",
    "\n",
    "            while q:\n",
    "                f, d, i, j = heappop(q)\n",
    "\n",
    "                if (i, j) not in visited:\n",
    "                    visited.add((i, j))\n",
    "                else:\n",
    "                    continue\n",
    "\n",
    "                if len(visited) > limit:\n",
    "                    return True\n",
    "\n",
    "                if target[0] == i and target[1] == j:\n",
    "                    return True\n",
    "\n",
    "                for a, b in ((i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1)):\n",
    "                    if 0 <= a < n and 0 <= b < n:\n",
    "                        if (a, b) not in blocked and (a, b) not in visited:\n",
    "                            f1 = d + 1 + h(a, b)\n",
    "                            heappush(q, (f1, d + 1, a, b))\n",
    "\n",
    "            return False\n",
    "\n",
    "        return search(source, target) and search(target, source)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isEscapePossible(self, blocked: List[List[int]], source: List[int], target: List[int]) -> bool:\n",
    "        \n",
    "        m = len(blocked)\n",
    "        dx = [-1, 0, 1, 0]\n",
    "        dy = [0, 1, 0, -1]\n",
    "        bset = [(x, y) for x, y in blocked]\n",
    "        L = int(1e6)\n",
    "        vis = set() \n",
    "        Q = deque([(0, source[0], source[1])])\n",
    "        vis.add(tuple(source))\n",
    "        flag = 0 \n",
    "        while Q:\n",
    "            d, x, y = Q.popleft() \n",
    "            if [x, y] == target:\n",
    "                return True\n",
    "            if d >= m:\n",
    "                flag = 1\n",
    "                break  \n",
    "            for i in range(4):\n",
    "                nx, ny = x+dx[i],y+dy[i]\n",
    "                if 0<=nx<L and 0<=ny<L and (nx, ny) not in bset and (nx, ny) not in vis:\n",
    "                    vis.add((nx, ny))\n",
    "                    Q.append((d+1, nx, ny))\n",
    "        if flag == 0:\n",
    "            return False \n",
    "        vis = set() \n",
    "        Q = deque([(0, target[0], target[1])])\n",
    "        vis.add(tuple(target))\n",
    "        while Q:\n",
    "            d, x, y = Q.popleft() \n",
    "            if d >= m:\n",
    "                return True \n",
    "            for i in range(4):\n",
    "                nx, ny = x+dx[i],y+dy[i]\n",
    "                if 0<=nx<L and 0<=ny<L and (nx, ny) not in bset and (nx, ny) not in vis:\n",
    "                    vis.add((nx, ny))\n",
    "                    Q.append((d+1, nx, ny))\n",
    "        return False \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isEscapePossible(self, blocked: List[List[int]], source: List[int], target: List[int]) -> bool:\n",
    "        b = {(x,y) for x,y in blocked}\n",
    "\n",
    "        def chk(s, tar):\n",
    "            vis = {}\n",
    "            d = deque()\n",
    "            d.append((s[0], s[1], 0))\n",
    "            outside = 0\n",
    "            while d:\n",
    "                x,y,t = d.popleft()\n",
    "                for u,v in [[x-1,y],[x,y-1],[x+1,y],[x,y+1]]:\n",
    "                    if 0<=u<1000000 and 0<=v<1000000 and (u,v) not in b and (u,v) not in vis:\n",
    "                        if (u,v) == tuple(tar):\n",
    "                            return 1\n",
    "                        vis[(u,v)] = 1\n",
    "                        if t > 210:\n",
    "                            outside = 1\n",
    "                        else:\n",
    "                            d.append((u,v,t+1))\n",
    "            if outside:\n",
    "                return 2\n",
    "            return 0\n",
    "        # print(chk(source, target), chk(target, source))\n",
    "        p,q = chk(source, target), chk(target, source)\n",
    "        if p == 1:\n",
    "            return True\n",
    "        elif p == 2 and q == 2:\n",
    "            return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isEscapePossible(self, blocked: List[List[int]], source: List[int], target: List[int]) -> bool:\n",
    "        blocked = set(map(tuple, blocked))\n",
    "        def dfs(x, y, target, seen):\n",
    "            if not (0 <= x < 10**6 and 0 <= y < 10**6) or (x, y) in blocked or (x, y) in seen: return False\n",
    "            seen.add((x, y))\n",
    "            if len(seen) > 20000 or [x, y] == target: return True\n",
    "            return dfs(x-1, y, target, seen) or dfs(x, y-1, target, seen) or dfs(x+1, y, target, seen) or dfs(x, y+1, target, seen)\n",
    "        return dfs(source[0], source[1], target, set()) and dfs(target[0], target[1], source, set())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isEscapePossible(self, blocked: List[List[int]], source: List[int], target: List[int]) -> bool:\n",
    "        MX = 10**6\n",
    "        blocked = set(map(tuple,blocked))\n",
    "        CNT = len(blocked)*(len(blocked)-1)//2\n",
    "        # print(CNT)\n",
    "        def dfs(cur,target,vis):\n",
    "            if cur == target or len(vis)>CNT:\n",
    "                # print(vis)\n",
    "                return True\n",
    "            x,y = cur\n",
    "            for nx,ny in (x+1,y),(x-1,y),(x,y+1),(x,y-1):\n",
    "                if nx>=MX or nx<0 or ny>=MX or ny<0 or (nx,ny) in blocked or (nx,ny) in vis:\n",
    "                    continue\n",
    "                vis.add((nx,ny))\n",
    "                if dfs([nx,ny],target,vis):\n",
    "                    return True\n",
    "            return False\n",
    "        res = dfs(source,target,set()) and dfs(target,source,set())\n",
    "        return res"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
